C-algae

Memory limit: 32 MB

C-algae is the Byteotians' favourite dish of their national cuisine. C-algae have a very specific structure. An algae consisting of a single cell is a c-algae. Two c-algae and , can be combined in either one of the following ways:

• by choosing all the cells from both and , and all the connections from both and ,
  

  

• by choosing all the cells from both and , all the connections from both and , and setting further connections: each cell from is connected to every cell from .
  

  

As a result we obtain a new c-algae .

Unfortunately the hostile country of Bitotia has recently started selling algae imitating c-algae. These look so alike that it is hard to tell the difference between a false one and a genuine c-algae. This is the reason why the Byteotian government has asked you to write a programme that would allow verification if a given algae is a c-algae.

Task

Write a programme that:

• reads the descriptions of algae from the standard input,
• checks which of them are proper c-algae,
• writes the answer to the standard output.

Input

In the first line of the standard input a single integer is written, , it denotes the number of algae to be examined. Descriptions of algae are written in the following lines. Each single description is of the following form: in the first line there are two integers written, separated by a single space, and , , . They denote the number of cells and the number of connections respectively. The cells are numbered from to . In the following lines the connections are described - each by two integers , , separated by a single space (, ), indicating that the cells and are connected. Each connection is specified once.

Output

lines should be written to the standard output. In the 'th line one word should be written:

• TAK - (i.e. yes in Polish) - if the 'th algae is a proper c-algae,
• NIE - (i.e. no in Polish) - otherwise.

Example

For the input data:

3
3 2
1 2
2 3
4 3
1 2
2 3
3 4
3 3
1 2
2 3
3 1

the correct result is:

TAK
NIE
TAK

Task author: Tomasz Walen.